package hot;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Num23 {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for(ListNode node : lists) {
            while(node != null) {
                priorityQueue.add(node);
                node = node.next;
            }
        }
        ListNode dummyhead = new ListNode(-1);
        ListNode cur = dummyhead;
        while (!priorityQueue.isEmpty()) {
            ListNode root = priorityQueue.poll();
            root.next = null;
            cur.next = root;
            cur = cur.next;
        }
        return dummyhead;
    }
}
